package problem.year2023.month04


/**
 * @author LiangMu
 * @version $Id: Day24.java, v 0.1 2023年04月27日 17:12 LiangMu Exp $$
 */
class Day24 {
    /**
     * 给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
     *
     * 示例 1：
     * 输入：s = "abab"
     * 输出："bab"
     * 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
     * 示例 2：
     *
     * 输入：s = "leetcode"
     * 输出："tcode"
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/last-substring-in-lexicographical-order
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    fun lastSubstring(s: String): String {
        val chars = s.toCharArray()
        val minChar = chars.max()
        val subStrList = ArrayList<String>()
        for (index in chars.indices) {
            if (chars[index] == minChar) {
                subStrList += s.substring(index)
            }
        }
        subStrList.sort()
        return subStrList.last()
    }

    fun lastSubstring2(s: String): String {
        val chars = s.toCharArray()
        val lastChar = chars.max()
        val subStrList = ArrayList<String>()
        var res = s
        for (index in chars.indices) {
            if (chars[index] == lastChar) {
                val substring = s.substring(index)
                val compareTo = s.compareTo(substring)
                if (compareTo < 0) {
                    res = substring
                }
            }
        }
        return res
    }

    companion object {
        fun lastSubstring2(s: String): String {
            val chars = s.toCharArray()
            val lastChar = chars.max()
            val subStrList = ArrayList<String>()
            var res = s
            for (index in chars.indices) {
                if (chars[index] == lastChar) {
                    val substring = s.substring(index)
                    res = if (res < substring) substring else res
                }
            }
            return res
        }
    }
}

fun main() {
    val s1 = "abab"
    println(Day24.lastSubstring2(s1))
}
